package com.zhanghp.class038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * O(2^n * n) <br/>
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合 <br/>
 * 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列 <br/>
 * 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合 <br/>
 * 比如输入：nums = [1,2,2] <br/>
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] <br/>
 * 测试链接 : https://leetcode.cn/problems/subsets-ii/ <br/>
 *
 * 剪枝策略：把多余的枝剪掉，不执行<br/>
 * 比如这个案例<br/>
 * [1,1,1,1,2,2,3] <br/>
 * 走0个1，走f(4) <br/>
 * 走1个1，走f(4) <br/>
 * 。。。
 * @author zhanghp
 * @since 2024/6/19 15:19
 */
public class Code02_Combinations {

    public static void main(String[] args) {
        List<List<Integer>> lists = new Code02_Combinations().subsetsWithDup(new int[]{1, 2, 3});
        lists.forEach(l -> {
            System.out.println( Arrays.toString(l.toArray()));
        });
    }

    /**
     * 先排好序<br/>
     * 进行相同数的挨个位置计数处理<br/>
     * [1,1,2,3]<br/>
     * 先处没有1，往下走的情况<br/>
     * 处理0位置的1，然后递归2,3<br/>
     * 在处理0,1位置的11，然后递归2,3 <br/>
     * ...<br/>
     *
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        f(nums, 0, new int[nums.length], 0, ans);
        return ans;
    }

    public void f(int[] nums, int cur, int[] path, int size, List<List<Integer>> ans){
        // 当cyr达到nums的长度时，进行path结果封装
        if (cur == nums.length) {
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                a.add(path[i]);
            }
            ans.add(a);
        }else {
            // 处理
            int j = cur + 1;
            // 找到下一组的不同数字
            while(j < nums.length && nums[j] == nums[cur]){
                j++;
            }
            // 进行没有第一组重复数字的处理 (第一次走进这个，为个空的子集， 然后走最后一组递归下面的for循环逻辑)
            f(nums, j, path, size, ans);
            // 你走完上面的递归的时候， size还是为0的，所以path[]在这重复利用
            // 遍历重复数字组的情况
            // [1,1,1,2,3]
            // 1 ...
            // 1,1...
            // 1,1,1...
            for (int i = cur; i < j; i++) {
                // 路径赋值
                path[size ++ ] = nums[cur];
                // 这个是从最后一组开始弄的，当走完上面的递归，开始走for循环里的递归
                // size 根据你指定 + 1
                // 然后走下一个for循环，可以理解为，size 是不变的 传入的就是size + 1
                f(nums, j, path, size , ans);
            }
        }
    }
}
